Gambler's Ruin Problem

Gambler's Ruin Problem: 두 도박꾼이 매 라운드마다 1달러씩가지고 내기를 할 때, 둘 중 어느 사람이 파산할 확률이 더 높은가?

결론은, 만약 어떤 한 사람이 이길 확률이 아주 조금이라도 작거나, 혹은 가지고 시작하는 돈이 조금이라도 적다면 그 사람이 매우 높은 확률로 지게 된다.

Assumption:

두 사람 A, B에 대하여 A가 $A$ 의 확률로 이긴다. 그럼 B는 $B = 1 - A$ 의 확률로 이기게 된다. 매 라운드마다 이 확률은 고정이다.
A는 $i$ 달러, B는 $N - i$ 달러를 가지고 게임을 시작한다.
$P_{i}$ 는 A가 $i$ 달러를 가지고 시작해서, 게임을 이기게 될 확률이다.
둘 중 한 사람이 모든 돈을 잃게 되어야만 게임이 끝나며, 게임이 도중에 끝나는 경우는 없다.

Solve

전체 확률의 법칙에 의하여, 둘 중 하나가 이기게 되는 경우( $P (K)$ : $K$ 는 둘 중 하나가 이기는 사건)는 다음과 같다.

P (K) = P (K ∣ A lose) P (A lose) + P (K ∣ A win) P (A win)

P_{i} = B P_{i - 1} + A P_{i + 1}

라는 2차 선형 동차 차분방정식이 만들어진다.

이 때, Boundary Condition은

$P_{0} = 0$ : A가 0원을 들고 시작할 때 이길 확률 ⇒ 0원이면 바로 지게 되므로 이길 확률은 0.
$P_{N} = 1$ : A가 N원을 들고 시작할 때 이길 확률 ⇒ N원이면 바로 이기게 되므로 이길 확률은 1. 으로 2개가 존재하니, 위 방정식은 해의 계수를 결정할 수 있다.

선형 동차 방정식이므로 특성방정식이 존재한다. $P_{i} = r^{i}$ 라고 할 때,

A r^{2} - r + B = 0

이 특성 방정식이 된다.

r = \frac{1 \pm 1 - 4 A B}{2 A} = \frac{1 \pm 1 - 4 A ( 1 - A )}{2 A} = \frac{1 \pm ( 1 - 2 A ) ^{2}}{2 A}

따라서 $r$ 의 가능한 값은

\frac{1 - A}{A}, 1

두 가지이다.

P_{i} = C_{1} (\frac{1 - A}{A})^{i} + C_{2} (1)^{i}

Boundary Condition을 대입하면

C_{1} = \frac{1}{( \frac{1 - A}{A} ) ^{N} - 1}, C_{2} = - \frac{1}{( \frac{1 - A}{A} ) ^{N} - 1}

P_{i} = \frac{( \frac{1 - A}{A} ) ^{i} - 1}{( \frac{1 - A}{A} ) ^{N} - 1} if A \neq = B = 1 - A

만약 A가 더 적은 돈을 가지고 시작한다면 어떻게 되는가?

이 경우에 대해서는 이길 확률이 같다고 가정하면 $A = B = \frac{1}{2}$ 이므로 위 $P_{i}$ 식의 $\frac{0}{0}$ 꼴이 되어 정의되지 않는다. 이를 해결하기 위해 $x = \frac{1 - A}{A}, lim_{x \to 1}$ 라고 하면

x \to 1 lim \frac{1 - x ^{i}}{1 - x ^{N}} = L’hopital \frac{i x ^{i - 1}}{N x ^{N - 1}} = \frac{i}{N}

즉, $i < N - i$ 라고 한다면 질 확률이 더 높을 수 밖에 없다.

같은 돈( $i = N /2$ )을 가지고 시작하더라도, A의 승률이 더 작은 불공평한 게임이라면 어떻게 되는가?
예를 들어 $A = 0.49$ 의 아주 작은 승률 차이라고 가정해보자.

P_{i} = \frac{( \frac{0.51}{0.49} ) ^{i} - 1}{( \frac{0.51}{0.49} ) ^{N} - 1} = \frac{( \frac{0.51}{0.49} ) ^{N /2} - 1}{( \frac{0.51}{0.49} ) ^{N} - 1}

N	$P_{i}$
20	0.4013
100	0.1192
200	0.018
각 판의 승률 차이는 아주 작더라도, $N$ 이 커질수록 큰 전체 승률 차이를 가지게 된다.